This invention relates to the field of broadband communications. More specifically, it relates to the design of virtual port schedulers for use in packet schedulers that are deployed within telecommunications switches.
Packet schedulers basically maintain queues of pointers to packets that are buffered in the switch memory, and determine the times at which each buffered packet is transmitted from the switch.
A conventional packet scheduler is implemented using a single monolithic component such as an application specific integrated circuit (ASIC), or a single software system. This one-component architecture has become undesirable however, for at least two reasons. The first reason is that the feature-set that has to be supported by schedulers has become too varied to be economically implemented on a single component. More particularly, as it has become necessary to implement a wider array of new features in packet schedulers, and as it has therefore become increasingly infeasible for switch manufacturers to implement a full feature-set in every packet scheduler, the need has arisen to design a customized scheduler for each specific type of packet switch that is produced. This trend, in turn, has driven up design costs for switch manufacturers.
A second reason for the undesirability of continuing with the use of a single monolithic component to implement a scheduler, arises because the definitions, let alone the implementations, of several of the aforementioned new scheduler features have yet to be stabilized. This means that switch designers have had to frequently redesign entire schedulers every time any unstable part of the overall feature-set changes.
Partitioning of an architecture involves mapping a plurality of features that have traditionally been implemented by a single component, to a plurality of components that replace the traditional single-component. Partitioning is difficult because the process demands that several factors be simultaneously considered. These factors include the requirement of implementing the total feature-set that was implemented by the single traditional component, using the plurality of components. The factors also include the preference that each component be mapped to a set of features whose implementations tend to change at the same time. Such mappings reduce upgrade costs for the entire architecture.
Another factor to be considered in partitioning an architecture is the desirability of mapping each set of features required to provide a single service, to the same component. Partitioned architectures that achieve this goal are hereinafter referred to as architectures that are partitioned along service-lines.
Another factor to consider in partitioning an architecture is the desire that the resulting components be decoupled from one another. Conventional telecommunication switch designs are constituted by components that are coupled to one another. Generally, the coupling of one component to another occurs when the designs of the components are highly interdependent on each other, such that one component cannot be changed without also changing the other. Coupling is generally undesirable as it prevents components from being developed independently of each other. Coupled components are decoupled from one another by implementing well-defined and simple interfaces between them, that do not have to change as the implementation of either of the components changes.
It is an object of this invention to obviate and/or mitigate one or more of the above-identified disadvantages.
According to a first broad aspect, the invention provides a method of virtual port scheduling in a packet switch having a plurality of virtual ports comprising the steps of: associating each virtual port with a traffic descriptor queue; for each traffic descriptor queue, maintaining a plurality of different statuses; combining the plurality of statuses to identify the next traffic descriptor queue which is to be served.
Preferably, the plurality of statuses include an eligibility for service status for each traffic descriptor queue which must be true for a given traffic descriptor queue to be served.
In a preferred embodiment, the step of maintaining a plurality of different statuses for each traffic descriptor queue comprises the steps of: determining for each traffic descriptor queue a first status indicative of whether a high priority criteria is satisfied; determining for each traffic descriptor queue a second status indicative of whether a medium priority criteria is satisfied; determining for each traffic descriptor queue a third status indicative of whether a low priority criteria is satisfied; if any traffic descriptor queue has a first status which is true then selecting such a traffic descriptor queue as the traffic descriptor queue to be served; if no traffic descriptor queue has a first status which is true and any traffic descriptor queue has a second status is true, then selecting such a traffic descriptor queue as the traffic descriptor queue to be served; if no traffic descriptor queue has a first status which is true and no traffic descriptor queue has a second status which is true, and any traffic descriptor queue has a third status which is true, then selecting such a traffic descriptor queue as the traffic descriptor queue to be served.
In another preferred embodiment, said step of maintaining a plurality of different statuses for each traffic descriptor queue identifier comprises the steps of: determining for each traffic descriptor queue a series of true-false statuses each indicative of whether a respective criteria having a respective certain priority ranging from higher to lower is satisfied; determining from all the statuses of all the traffic descriptor queues which ones have the highest priority true-status; and selecting any traffic descriptor queue with said highest priority status set to true as the traffic descriptor queue to be served.
Preferably, each virtual port handles a respective plurality of connections, each having an internal connection number, further comprising the steps of: maintaining a per connection queue for each internal connection number consisting of a queue of packet identifiers waiting to be de-queued; queueing per connection queue identifiers in each said traffic descriptor queue; wherein serving a traffic descriptor queue comprises dequeueing one of said per connection queue identifiers from the traffic descriptor queue to be served, and dequeueing a packet identifier from the per connection queue identified by the dequeued per connection queue identifier, and outputting a packet identified by the packet identifier.
According to another broad aspect, the invention provides a virtual port scheduler hardware block for use in a packet scheduler and having an interface for sending and receiving traffic descriptor queue identifiers from the remainder of the packet scheduler, each traffic descriptor queue identifier identifying a traffic descriptor queue for a given virtual port, the virtual port scheduler comprising: a status element for maintaining a plurality of statuses for each of a plurality of said traffic descriptor queue identifiers on the basis of traffic descriptor queue identifiers output by the virtual port scheduler through said interface; a status encoder for forming a combination of the statuses maintained by the status element and selecting on the basis of the combination one of said traffic descriptor queue identifiers and outputting this through said interface, thereby identifying the next traffic descriptor queue to be served.
According to another broad aspect, the invention provides a virtual port scheduler comprising means for associating each of a plurality of virtual ports with a respective traffic descriptor queue; status maintaining means for maintaining a plurality of different statuses for each traffic descriptor queue; combining means for combining the plurality of statuses to identify the next traffic descriptor queue which is to be served. Preferably, the status maintaining means and said combining means comprise means for determining for each traffic descriptor queue a series of true-false statuses each indicative of whether a respective criteria having a respective certain priority ranging from higher to lower is satisfied, means for determining from all the statuses of all the traffic descriptor queues which ones have the highest priority true-status, and means for selecting any traffic descriptor queue with said highest priority status set to true as the traffic descriptor queue to be served.